1. Field of the Invention
The present invention relates to compilers for computer systems and processors. More specifically, the present invention relates to code optimizers and schedulers for usage in a just-in-time (JIT) compiler.
2. Description of the Related Art
The Internet is regarded by many as the fastest growing market on Earth. In the 1990s, the number of Internet users has grown exponentially. In June of 1995, an estimated 6.6 million hosts were connected, an increase of nearly 5 million hosts in a mere six months. The current growth rate on the Internet is approximately 75% per year. In June of 1995, the 6.6 million hosts included approximately 120,000 networks and over 27,000 web servers. The number of web servers is doubling approximately every 53 days.
Various technical innovations have proven highly suited to the Internet environment. For example, in 1990 programmers at Sun Microsystems developed a universal programming language, eventually known as "the Java.TM. programming language". Sun, Sun Microsystems and the Sun Logo are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries. All SPARC trademarks, including UltraSPARC I and UltraSPARC II, are used under license and are trademarks of SPARC International, Inc. in the United States and other countries. Products bearing SPARC trademarks are based upon an architecture developed by Sun Microsystems, Inc.
The Java.TM. programming language resulted from programming efforts intended for coding in the C++ language. The Java.TM. programming language thus has many commonalities with C++ but is further regarded as a simple, object-oriented, distributed, interpreted yet high performance, robust yet safe, secure, dynamic, architecturally neutral, portable, and multi-threaded language. The Java.TM. programming language has emerged as the programming language of choice for the Internet. Many large software and hardware companies have licensed the Java.TM. programming language from Sun Microsystems.
A highly advantageous characteristic of the Java.TM. programming language is architectural independence that allows a compiled Java.TM. program to run on any computer. A Java.TM. compiler achieves architectural independence by generating an intermediate language that is further converted into multiple highly diverse machine languages that execute in different processors. The intermediate language form used in the Java.TM. programming language is called a bytecode representation, a set of byte-sized codes representing different commands.
Bytecodes are executed either through usage of a bytecode interpreter or a just-in-time (JIT) compiler. An interpreter is a program that reads bytecodes and executes the operations indicated by the bytecodes. Multiple diverse processors respectively use different interpreters to convert the bytecodes into the particular machine representations that are executable on the processors. Unfortunately, interpretive computer languages are traditionally very slow due to the overhead of executing an intermediate program, the interpreter, in addition to the bytecode execution.
In contrast to interpretation of bytecodes, dynamic or just-in-time (JIT) compilation reads the bytecodes, translates the bytecodes directly into the machine language of the target processor without executing the machine language instructions. Once the bytecodes are compiled, the just-in-time (JIT) compiler terminates and passes control to the machine language version of the bytecode program. The machine language program executes directly on the target processor. The just-in-time (JIT) compiled program executes much faster than a program that is executed in the interpretive environment.
A compiler generally operates in two stages, a code generation stage and an optimization stage. A just-in-time (JIT) compiler, in contrast, typically only includes the code generation stage since any increase in performance gained by optimization is overburdened by the time expended in the optimization process. Some form of scheduling may be useful for just-in-time (JIT) compilers that are used to generate code for in-order superscalar processors, since the code generated by a just-in-time (JIT) compiler has a generally sequential nature. However, the JIT compiler generates code for one bytecode at a time and, due to time constraints, does not reschedule the generated code stream. Ignoring memory stall conditions, typical code streams generated by JIT compilers have an effective scalarity of 1. Accordingly a superscalar processor only executes one instruction at a time, essentially eliminating advantages gained by a superscalar processor over a conventional scalar processor.
Scheduling of instructions is needed to increase the effective usage of superscalar processors by reducing dependences between instructions. Current JIT compilers do not schedule instructions because instruction scheduling is a compile phase that is highly time consuming. A just-in-time (JIT) compiler improves program performance in comparison to performance of an interpreted program only if the compile time of the program is less than timing efficiency improvements achieved in execution of the program.
Traditional compilers employ schedulers such as directed acyclic graph (DAG) schedulers that have a complexity and thus an execution time proportional to the number of instructions squared (an N.sup.2 complexity). The time duration of scheduling and thus compiling becomes large for instruction blocks with a large number of instructions.
What is needed is a fast technique for scheduling that improves the overall performance of a program executing in a just-in-time (JIT) compiler environment.